In computer systems where multiple disk drives are available, data may replicated and stored redundantly to reduce the risk of losing data when hardware failure occurs. The redundancy of data in such a system is intentional so that when a disk drive fails, the computer system can access the same data from the redundant disk drive. In addition to the intentional redundancy to reduce risk of data loss, unintentional redundant data may exist in a computer system. For example, multiple users of a shared system may store the same data item, or the same data item may be stored at different times. This duplication increases the size and therefore the cost of the system.
One solution to optimize the storage size is to store only one instance of the unique portion of each data item. Each data item, or asset, may be made up of asset parts. Some asset parts may be unique and other asset parts may be non-unique. The non-unique asset parts contain the same data and metadata as another asset or asset part, and the unique asset parts are the asset parts for which no match is found on the system or which are unique by their nature. For example, every asset has at least one unique portion because, by its nature, every asset is ingested into the storage system at a unique time. The system stores only one instance of a non-unique asset part, and this non-unique asset part would be referenced by the multiple assets or asset parts that contain that same non-unique portion. Thus, when users retrieve the multiple unique assets, they retrieve the related, non-unique asset parts from the same storage location.
For example, multiple users may receive the same email with an attachment. Each received email would have the same body and attachment, which are the non-unique asset parts associated with the email. However, each email is unique because it has a unique time received, status, flags, or other user-specific information. By storing the body and attachment only once, if five recipients store the same email, the storage system maintains only the five unique portions of the emails, one copy (or replica) of the body, and one replica of the attachment. Without such single instance storage mechanisms, the system would have to store the five unique portions of the emails, five replicas of the body, and five replicas of the attachment.
Further, in systems where redundancy is purposefully implemented, such as in a RAID 1 mirrored configuration, without single instance storage, the RAID 1 mirrored system would store ten emails (two replicas of each unique portion of the emails), ten replicas of the body, and ten replicas of the attachment. Instead, with single instance storage of non-unique asset parts as described above, the RAID 1 system would only store ten emails, two replicas of the body, and two replicas of the attachment. Thus, single instance storage of non-unique asset parts is even more advantageous in systems where even more redundancy is purposefully implemented.
To maintain the information necessary to reconstruct the original asset, some single instance storage systems maintain forward references from the asset to its asset parts. Using these forward references, the system can identify all asset parts that make up the original asset. In addition, such systems may use backward references from an asset part to the asset, or assets, that refer to it. Using these backward references, or “back references,” the system can determine when the asset part can be safely destroyed or deleted (i.e. when the asset part has no back references to any assets).
Instead of maintaining the actual back references to assets in the data storage system, some such systems maintain a back reference count for each asset part. When such a system receives instructions to destroy an asset having asset parts, the system checks the asset's forward references to identify the corresponding asset parts. The system then checks the backward reference count of each corresponding asset part, decrements the back reference count by one, and if the count reaches zero, the system is authorized to destroy that asset part. However, if the backward reference count is non-zero after decrementing, the system will not destroy that asset part because the asset part is associated with another asset.
Implementing single instance storage of non-unique asset parts in redundant storage systems presents numerous problems because the forward references and backward references (or back reference count) for the asset and asset part replicas, which may be distributed across multiple nodes in the system, must also be maintained. One method to maintain an accurate back reference count in a distributed storage system utilizes distributed transactions, traditionally implemented using the two-phase commit protocol. However, this solution requires coordination among multiple nodes (or servers), is subject to interruption when one of the servers fails, and is difficult to scale when adding more servers to the system.